package hzk.codex2016.tree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class BSTs {
	/**
	 * https://leetcode.com/problems/unique-binary-search-trees-ii/
	 * 
	 * @param n
	 * @return
	 */
	public List<TreeNode> generateTrees(int n) {
		class S {
			TreeNode copy(TreeNode src) {
				if (src == null)
					return null;
				TreeNode cpy = new TreeNode(src.val);
				cpy.left = copy(src.left);
				cpy.right = copy(src.right);
				return cpy;
			}

			List<TreeNode> genTrees(int n, int x) {
				if (n == 0) {
					return Collections.singletonList(null);
				}
				if (n == 1) {
					return Collections.singletonList(new TreeNode(x));
				}
				TreeNode me;
				List<TreeNode> ret = new ArrayList<>();
				List<TreeNode> lefts, rights;
				for (int i = 0; i < n; i++) {
					lefts = genTrees(i, x);
					rights = genTrees(n - 1 - i, x + i + 1);

					for (TreeNode left : lefts) {
						for (TreeNode right : rights) {
							me = new TreeNode(x + i);
							me.left = copy(left);
							me.right = copy(right);
							ret.add(me);

						}
					}
				}

				return ret;
			}
		}

		S s = new S();
		if (n == 0)
			return Collections.emptyList();
		return s.genTrees(n, 1);

	}

	/**
	 * https://leetcode.com/problems/unique-binary-search-trees/
	 * 
	 * @param n
	 * @return
	 */
	public int numTrees(int n) {
		int[] r = new int[30];
		r[1] = r[0] = 1;
		for (int x = 2; x <= n; x++) {
			int s = 0;
			for (int i = 0; i < x; i++) {
				s += r[i] * r[x - i - 1];
			}
			r[x] = s;
		}

		return r[n];
	}

	/**
	 * https://leetcode.com/problems/validate-binary-search-tree/
	 * 
	 * @param root
	 * @return
	 */
	public boolean isValidBST(TreeNode root) {
		if (root == null)
			return true;
		TreeNode pre = null, p;
		Stack<TreeNode> st = new Stack<>();
		for (p = root; p != null; p = p.left)
			st.push(p);

		while (!st.empty()) {
			p = st.pop();
			if (pre != null && pre.val >= p.val)
				return false;
			pre = p;
			for (p = p.right; p != null; p = p.left)
				st.push(p);
		}
		return true;

	}

	/**
	 * https://leetcode.com/problems/recover-binary-search-tree/
	 * 
	 * @param root
	 */
	public void recoverTree(TreeNode root) {
		if (root == null)
			return;
		TreeNode pre, p;
		TreeNode err1 = null, err2 = null;
		Stack<TreeNode> st = new Stack<>();
		for (p = root; p != null; p = p.left)
			st.push(p);
		pre = st.peek();
		while (!st.empty()) {
			p = st.pop();
			if (pre.val > p.val) {
				if (err1 == null) {
					err1 = pre;
					err2 = p;
				} else {
					err2 = p;
				}

			}
			;
			pre = p;
			for (p = p.right; p != null; p = p.left)
				st.push(p);
		}

		int t = err1.val;
		err1.val = err2.val;
		err2.val = t;

	}

	public static void main(String[] args) {
		BSTs me = new BSTs();
		// List<TreeNode> ans = me.generateTrees(4);
		// for (TreeNode a : ans) {
		// Trees.print(a);
		// System.out.println(me.isValidBST(a));
		// }
		// for (int i = 0; i < 24; i++) {
		// System.out.printf("numTrees(%d)=%d\n", i, me.numTrees(i));
		// }
		//
		// System.out.println(me.isValidBST(Trees.from(10,5,15,-1,-1,6,20)));

		//TreeNode tree2 = Trees.from(4,2,-1,3,-1,-1,-1,1);
		TreeNode tree2 = Trees.from(8, 3, 7, -1, -1, 5, 4);
		Trees.print(tree2);
		me.recoverTree(tree2);
		Trees.print(tree2);

	}
}
